//  给定一个整数数组nums， 再给定一个整数k，表示大小为k的滑动窗口从数组的最左侧移动到数组的最右侧，我们只能看到滑动窗口内的k个数字，滑动窗口每次只能向右移动一位
//  要求返回滑动窗口中的最大值

// 思路，滑动窗口维护一个单调队列（单调递减），把当前元素和队列中的队尾的元素比较
// 如果前者大于后者，则把队尾的元素移除，直到队列为空或者当前元素小于队尾的元素
// 当队头元素不在窗口中时，从队头出

function maxSlidingWindow(nums, k) {
    let queue = []
    let result = []
    for (let i = 0; i < nums.length; i++) {
        // 当队头元素不在窗口中时，从队头出
        if (i >= k && nums[i - k] === queue[0]) {
            queue.shift()
        }        
        // 当前元素大于队尾的元素，从队尾出
        while (queue.length && queue[queue.length - 1] < nums[i]) {
            queue.pop()
        }
        queue.push(nums[i])
        // 当达到k个数的时候，记录最大值
        if (i >= k - 1) {
            result.push(queue[0])
        }
    }
    return result
}

let nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
console.log(maxSlidingWindow(nums, k));